package leetcode.题库.动态规划;

/**
 * 最小路径和
 *
 * @author yanzhenming
 * @date 2023/4/14  17:04
 */

/**
 * 描述
 *
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 */

/**
 * 思路
 */
public class Solution64 {

    public static void main(String[] args) {
        int[][] arr = new int[][]{{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(minPathSum(arr));
    }

    public static int minPathSum(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < row; i++) dp[i][0] = grid[i][0] + dp[i-1][0];
        for (int i = 1; i < col; i++) dp[0][i] = grid[0][i] + dp[0][i-1];
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                int cur = grid[i][j];
                dp[i][j] = Math.min(cur + dp[i-1][j], cur + dp[i][j-1]);
            }
        }
        return dp[row-1][col-1];
    }

}
